package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/23 17:29
 * 桶排序
 * 根据条件创建几个桶，根据数组的最大值和最小值创建桶的数量, bucketNum = (max - min) / nums.length + 1;
 * 然后把元素放入对应的桶中, index = (num - min) / nums.length
 * 桶里面再排序, 因为桶是已经排序好了的
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] nums = new int[]{4, 2, 3, -9, 10, 8};
        tong(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(Math.ceil(8.0/ 3));
    }

    public static void tong(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int bucketSize = (int)Math.ceil((double)(max - min) / nums.length);
        System.out.println(bucketSize);
        List<List<Integer>> bucket = new ArrayList<>(bucketSize);
        for (int i = 0; i < bucketSize; i++) bucket.add(new ArrayList<>());
        for (int num : nums) {
            int index = (num - min) / nums.length;
            bucket.get(index).add(num);
        }
        int index = 0;
        for (List<Integer> list : bucket) {
            if (list.isEmpty()) continue;
            Collections.sort(list);
            for (int num : list) nums[index++] = num;
        }
    }

    private static void bucketSort(int[] nums) {
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        int bucketLen = (max - min) / nums.length + 1;
        List<List<Integer>> bucket = new ArrayList<>(bucketLen);
        for (int i = 0; i < bucketLen; i++) bucket.add(new ArrayList<>());
        for (int num : nums) {
            int tmp = (num - min) / nums.length;
            bucket.get(tmp).add(num);
        }
        for (List<Integer> list : bucket) Collections.sort(list);
        int idx = 0;
        for (int i = 0; i < bucketLen; i++) {
            for (Integer num : bucket.get(i)) {
                nums[idx++] = num;
            }
        }
    }

}
